i=1∑nlcm(i,n)
i=1∑ngcd(i,n)i∗n
ni=1∑ngcd(i,n)i
nd∣n∑i=1∑n[gcd(i,n)=d]di
nd∣n∑i=1∑dn[gcd(i,dn)=1]i
nd∣n∑i=1∑d[gcd(i,d)=1]i
令 f(n)=∑i=1ni[gcd(i,n)=1],g(n)=∑i∣nf(i)
f(n)=21i=1∑ni[gcd(i,n)=1]+(n−i)[gcd(n−i,n)=1]
=21i=1∑nn[gcd(i,n)=1]
=2ni=1∑n[gcd(i,n)=1]
=2n×φ(n)
枚举因数预处理 g(n),注意一下 f(1)=1。
答案为:n×g(n)
#include <cstdio>
const int MAXN = 1000000;
int t , n , k , prime[ MAXN + 5 ] , phi[ MAXN + 5 ];
long long g[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
phi[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
phi[ i ] = i - 1;
}
for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
phi[ i * prime[ j ] ] = phi[ i ] * prime[ j ];
break;
}
phi[ i * prime[ j ] ] = phi[ i ] * ( prime[ j ] - 1 );
}
}
for( int i = 1 ; i <= MAXN ; i ++ )
for( int j = i ; j <= MAXN ; j += i )
g[ j ] += i == 1 ? 1 : 1ll * phi[ i ] * i / 2;
}
int main( ) {
sieve( );
scanf("%d",&t);
while( t -- ) {
scanf("%d",&n);
printf("%lld\n", n * g[ n ] );
}
return 0;
}